허프만 코드 알고리즘

2018-01-19

####기본 개념

허프만 코드는 압축에서 기본적으로 쓰이는 개념으로 자주 쓰이는 문자열에 대해 적은 비트를 할당하여 문자를 압축하는 알고리즘이다. -> 예를 들어 “AABBABAAACDEKSPEQAAA” 라는 문자열이 있을 때 여기서 사용되는 A라는 문자열은 가장 많이 쓰이므로 이를 압축할 때 가장 적은 비트수를 가지는 0과 같은 비트로 매칭하여 이를 대체한다.

허프만 코드는 원래 파일의 크기를 효과적으로 압축할 수 있는 장점이 있기 때문에 기본적으로 압축 기술에 널리 쓰인다.

####동작 원리

허프만 알고리즘의 기본적인 동작은 이러하다.

압축할 문자열의 빈도수를 계산한다.
빈도수를 바탕으로 문자열을 정렬한다.
정렬된 문자열을 2개씩 꺼내 묶어 트리 형태로 만든다. 꺼낸 2개의 빈도수는 빈도수를 합친 Node 형태로 다시 문자열 리스트에 집어 넣는다.
2~3 과정을 반복하며 트리가 완성되면 끝낸다.

위의 과정에서 Node를 합치고 다시 넣은 다음 또 빈도수대로 정리하는 과정을 하기 위해서 sort를 여러번 호출할 수는 없기 때문에 여기서는 우선순위 큐를 이용해 원소를 넣을때 마다 자동으로 정렬하게 한다. 트리를 구성하기 위한 Node 들을 우선순위 큐에 집어 넣은뒤 우선순위 큐의 사이즈가 1이 될 때까지 트리를 반복적으로 구성해 나간다.

최후에 완성되어 queue에 남은 것은 root 노드가 되며 이 루트 노드를 기준으로 왼쪽은 0, 오른쪽은 1을 할당하여 리프노드를 찾을 때까지 탐색해 나가게 된다. -> 문자들은 모두 리프노드에 할당되며 그때까지 지나온 0과 1의 경로들이 인코딩되는 값이다.

이 인코딩 값을 매번 찾는 것이 한번에 찾기 위해서 밑에 코드에서는 map을 사용하여 문자와 인코딩값을 저장해 두었다. 그리고 인코딩 할 때 map에서 찾아 해당되는 인코딩 값들을 문자열로 이어나가면 인코딩된 값을 찾을 수 있다. -> 문자열 만큼만 반복하면 되니 O(n) 시간이 걸린다.

디코딩 과정에서는 인코딩된 문자열을 다시 원래의 문자로 돌리기 위해 트리를 검색한다. 루트를 기준으로 문자열의 i번쨰가 0이면 왼쪽트리, 1이면 오른쪽 트리로 따라가며 리프노드를 만나게 될경우 그 리프노드의 데이터를 출력하고 현재 노드를 다시 루트로 되돌리는 과정을 반복한다. -> 이 과정도 문자열 만큼 반복되므로 O(n)이다.

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
#include<map>

using namespace std;

map<char, string> encode;


typedef struct Node
{
	int pri;
	char data;
	Node* left;
	Node* right;
}Node;

typedef struct
{
	bool operator()(const Node* a, const Node* b)
	{
		return a->pri > b->pri;
	}
}NodeCompare;


Node datas[] = { { 67, 'A', NULL, NULL }, { 23, 'B', NULL, NULL }, { 13, 'D', NULL, NULL },
{ 19, 'C', NULL, NULL }, { 10, 'E', NULL, NULL }, { 5, 'F', NULL, NULL } };


void dfs(Node* n,string code)
{
	if (n->left == NULL && n->right == NULL && n->data != ' ')
	{
		encode.insert(make_pair(n->data, code));
		cout << n->data << " : " << code << endl;
		return;
	}
	if (n->left != NULL)
	{
		dfs(n->left, code+'0');
	}
	if (n->right != NULL)
	{
		dfs(n->right, code + '1');
	}
}

string encoding(string s)
{
	string result = "";
	for (int i = 0; i < s.length(); i++)
	{
		result += encode.find(s[i])->second;
	}
	return result;
}

string decode(Node* root, string s)
{
	Node* current = root;
	string result = "";
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '0')
			current = current->left;
		if (s[i] == '1')
			current = current->right;

		if (current->left == NULL && current->right == NULL)
		{
			result+=current->data;
			current = root;
		}
	}
	return result;
}

int main()
{
	priority_queue<Node*,vector<Node*>, NodeCompare> pq;

	for (int i = 0; i < 6; i++)
	{
		Node* target = new Node(datas[i]);
		pq.push(target);
	}

	while (pq.size() != 1)
	{
		Node* left = pq.top();
		pq.pop();
		Node* right = pq.top();
		pq.pop();
		
		int newVal = (left->pri) + (right->pri);
		pq.push(new Node({ newVal, ' ', left, right }));
	}
	
	Node* root = pq.top();
	pq.pop();

	cout << "encoding list:" << endl;
	dfs(root, "");
	cout << endl << endl;


	string target = "ABCFFDEFABCBFFEEDDAABAB";
	cout << "original string   ->   "<<target<<endl;
	string result = encoding(target);
	cout << "converted   ->   "<< result<<endl;
	cout << target.size() * 8 << "bit is converted to " << result.size()<<endl<<endl<<endl;

	
	cout<<"converted   ->   "<<result<<"\ndecode result  ->  "<<decode(root, result);

	return 0;
}

Gunner

ProgrammingAlgorithm

허프만 코드 알고리즘